﻿/*
 * Big Number
 * Represents a very big number
 * 
 * ATTENTION:
 *  this is a very lightweighted implementation that only contains the functions which
 *  DHT needs
 * 
 * ALL numbers are in Little-Ending! Low bytes are in Low address spaces
 * 
 * BigInteger is unsigned!
 * 
 * BigInteger cannot modify after generated
 * 
 * Author: snowdreamist
 * Date: 2011/11/22
 * 
 */


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using BitTorrentSharp.Helpers;

namespace BitTorrentSharp.Maths
{
    /// <summary>
    /// Represents a very big number
    /// </summary>
    public class BigInteger: 
        IEquatable<BigInteger>, 
        IEquatable<UInt64>,
        IComparable,
        IComparable<BigInteger>,
        IComparable<UInt64>
    {
        #region static
        /// <summary>
        /// zero
        /// </summary>
        public readonly static BigInteger Zero = new BigInteger(new UInt64[] { 0 });
        /// <summary>
        /// Xor
        /// </summary>
        public static BigInteger operator^(BigInteger int1, BigInteger int2)
        {
            if (int1 == null)
                throw new ArgumentNullException("int1");
            if (int2 == null)
                throw new ArgumentNullException("int2");
            return new BigInteger(BinaryHelper.Xor(int1._number, int2._number));
        }
        /// <summary>
        /// >
        /// </summary>
        public static bool operator>(BigInteger int1, BigInteger int2)
        {
            if (int1 == null)
                throw new ArgumentNullException("int1");
            if (int2 == null)
                throw new ArgumentNullException("int2");
            return int1.CompareTo(int2) == 1;
        }
        /// <summary>
        /// >=
        /// </summary>
        public static bool operator >=(BigInteger int1, BigInteger int2)
        {
            if (int1 == null)
                throw new ArgumentNullException("int1");
            if (int2 == null)
                throw new ArgumentNullException("int2");

            int r = int1.CompareTo(int2);
            return r == 1 || r == 0;
        }
        /// <summary>
        /// <
        /// </summary>
        public static bool operator <(BigInteger int1, BigInteger int2)
        {
            if (int1 == null)
                throw new ArgumentNullException("int1");
            if (int2 == null)
                throw new ArgumentNullException("int2");
            return int1.CompareTo(int2) == -1;
        }
        /// <summary>
        /// <=
        /// </summary>
        public static bool operator <=(BigInteger int1, BigInteger int2)
        {
            if (int1 == null)
                throw new ArgumentNullException("int1");
            if (int2 == null)
                throw new ArgumentNullException("int2");

            int r = int1.CompareTo(int2);
            return r == -1 || r == 0;
        }
        /// <summary>
        /// ==
        /// </summary>
        public static bool operator==(BigInteger int1, BigInteger int2)
        {
            if (int1 == null)
                throw new ArgumentNullException("int1");
            if (int2 == null)
                throw new ArgumentNullException("int2");
            return int1.CompareTo(int2) == 0;
        }
        /// <summary>
        /// !=
        /// </summary>
        public static bool operator !=(BigInteger int1, BigInteger int2)
        {
            if (int1 == null)
                throw new ArgumentNullException("int1");
            if (int2 == null)
                throw new ArgumentNullException("int2");
            return int1.CompareTo(int2) != 0;
        }
        /// <summary>
        /// Compare to, in little ending
        /// </summary>
        /// <param name="number"></param>
        /// <returns></returns>
        public static int CompareTo(UInt64[] int1, UInt64[] int2)
        {
            if (int1 == null)
                throw new ArgumentNullException("int1");
            if (int2 == null)
                throw new ArgumentNullException("int2");

            if (int1.Length > int2.Length)
            {
                // check int1 high bits, if non-zero exists, then, int1 is larger, return 1
                for (int i = int1.Length - 1; i >= int2.Length; --i)
                    if (int1[i] != 0)
                        return 1;
            }
            else if (int2.Length > int1.Length)
            {
                // check int2 high bits, if non-zero exists, then, int2 is larget, return -1
                for (int i = int2.Length - 1; i >= int1.Length; --i)
                    if (int2[i] != 0)
                        return -1;
            }

            // start from min length
            int length = Math.Min(int1.Length, int2.Length);
            // find the first index of element that is non-zero, compare the indexes, the larger index the larger number
            // if indexes are equal, then, compare the values, the larger value the larger number
            int index1 = length - 1, index2 = length - 1;

            while (index1 > -1 && int1[index1] == 0) --index1;
            while (index2 > -1 && int2[index2] == 0) --index2;

            if (index1 == index2)
            {
                if (index1 == -1)
                    // all reach the end, both are zero, equal
                    return 0;
                else
                    // compare value
                    return int1[index1].CompareTo(int2[index2]);
            }
            else
            {
                return index1 > index2 ? 1 : -1;
            }
        }
        #endregion
        /// <summary>
        /// constructor
        /// </summary>
        /// <param name="number">number in bytes</param>
        public BigInteger(byte[] number) : this(number.ConvertToUInt64s()) { }
        /// <summary>
        /// constructor
        /// </summary>
        /// <param name="number">number in UInt64</param>
        public BigInteger(UInt64[] number)
        {
            if (number == null)
                throw new ArgumentNullException("number");
            // copy
            this._number = new UInt64[number.Length];
            number.CopyTo(this._number, 0);
        }

        #region private
        /// <summary>
        /// number
        /// </summary>
        private UInt64[] _number;

        #endregion

        /// <summary>
        /// divided by 2
        /// </summary>
        /// <returns></returns>
        public BigInteger DividedBy2()
        {
            int index = this._number.Length - 1;

            while (index > -1 && this._number[index] == 0) --index;

            if (index == -1)
                // zero
                return Zero;

            // copy
            UInt64[] newNumber = this._number.Take(index + 1).ToArray();

            for (int i = 0; i < newNumber.Length - 1; ++i)
                newNumber[i] = ((newNumber[i + 1] & (UInt64)1) << 63) | (newNumber[i] >> 1);
            newNumber[newNumber.Length - 1] = newNumber[newNumber.Length - 1] >> 1;

            return new BigInteger(newNumber);
        }
        /// <summary>
        /// Number length in bytes
        /// </summary>
        public int BytesLength
        {
            get
            {
                return this._number.Length * 8;
            }
        }
        /// <summary>
        /// To bytes
        /// </summary>
        /// <returns></returns>
        public byte[] ToBytes()
        {
            return this._number.ConvertToBytes();
        }
        /// <summary>
        /// To uint64s
        /// </summary>
        public UInt64[] ToUInt64s()
        {
            UInt64[] result = new UInt64[this._number.Length];
            this._number.CopyTo(result, 0);
            return result;
        }

        #region equal and hash

        public override int GetHashCode()
        {
            return this._number.GetUInt64HashCode();
        }

        public override bool Equals(object obj)
        {
            try
            {
                return this.CompareTo(obj) == 0;
            }
            catch
            {
                return false;
            }
        }

        public bool Equals(BigInteger other)
        {
            return this.CompareTo(other) == 0;
        }

        public bool Equals(UInt64 other)
        {
            return this.CompareTo(other) == 0;
        }

        #endregion

        #region compare

        public int CompareTo(object obj)
        {
            if (obj is BigInteger)
                return this.CompareTo(obj as BigInteger);
            else if (obj is UInt64)
                return this.CompareTo((UInt64)obj);
            else if (obj is UInt16)
                return this.CompareTo((UInt64)(UInt16)obj);
            else if (obj is UInt32)
                return this.CompareTo((UInt64)(UInt32)obj);
            else
                throw new ArgumentException(String.Format("Cannot compare with type {0}", obj.GetType().Name));
        }

        public int CompareTo(BigInteger other)
        {
            return CompareTo(this._number, other._number);
        }

        public int CompareTo(UInt64 other)
        {
            return CompareTo(this._number, new UInt64[] { other });
        }

        #endregion
    }
}
